<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8" />
		<meta name="keywords" content="spring,Spring,java,web,程序员,博客,IT,技术,移动开发,Web前端,企业架构,编程语言,互联网,数据库,技术博客,blog,分布式架构,分布式">
		<meta name="description" content="cdcoder是一个程序员学习交流平台，深度IT技术博客，移动开发博客,Web前端博客,企业架构博客,编程语言博客,互联网博客,数据库博客,IT blog,核心关注IT知识传播，共享。为更好的IT产业贡献一份微薄的力量。">
		<link rel="shortcut icon" href="/img/code.ico" />
		<link rel="bookmark" href="/img/code.ico" />
		<title>java相关知识</title>
		<link href="../css/index.css" rel="stylesheet">
		<link href="../css/github.css" rel="stylesheet" />
		<style>
			body {
				font-size: 16px;
				font: 400 16px/1.62 Georgia, "Xin Gothic", "Hiragino Sans GB", "Droid Sans Fallback", "Microsoft YaHei", sans-serif;
				font-family: 'PT serif', 微軟正黑體, 微软雅黑, 华文细黑, Microsoft Yahei, Hiragino Sans GB, sans-serif;
				color: #D0CCCC;

				text-shadow: 0px 0px 1px rgba(24, 22, 22, 0.35);
				background-color: #000;
			}
			table {
				border:2;
				border-color:#F3F3F3; ;
			}
				p{ text-indent:2em; padding:0px; margin:0px; }
		</style>
	</head>
	<body>

		<header>
			<div class="logo"><a href="/index.html">徐思润博客</a></div>
			<nav>
				<ul id="starlist">
					<li><a href="/java/index.html">java</a></li>
					<li><a href="/data/index.html">算法与数据结构</a></li>
					<li><a href="/db/mysql.html">数据库</a></li>
					<li><a href="/distribution/index.html">分布式</a></li>
					<li><a href="/framework/index.html">架构</a></li>
					<li><a href="/interview/index.html">面试与被面试</a></li>
					<li><a href="/live/index.html">日常生活</a></li>
					<li><a href="/about.html">关于我</a></li>
					<li><a href="/baby/index.html">baby墙</a></li>
				</ul>
			</nav>
		</header>
		<div class="box">

			<h3>排序表格版</h3>
			<hr />
			<figure>
				<table  border="2">
					<thead>
						<tr>
							<th>排序方法</th>
							<th>时间复杂度（平均）</th>
							<th>时间复杂度（最坏)</th>
							<th style='text-align:center;'>时间复杂度（最好)</th>
							<th>空间复杂度</th>
							<th>稳定性</th>
							<th>复杂性</th>
						</tr>
					</thead>
					<tbody>
						<tr>
							<td>直接插入排序</td>
							<td>O(n2)O(n2)</td>
							<td>O(n2)O(n2)</td>
							<td style='text-align:center;'>O(n)O(n)</td>
							<td>O(1)O(1)</td>
							<td>稳定</td>
							<td>简单</td>
						</tr>
						<tr>
							<td>希尔排序</td>
							<td>O(nlog2n)O(nlog2n)</td>
							<td>O(n2)O(n2)</td>
							<td style='text-align:center;'>O(n)O(n)</td>
							<td>O(1)O(1)</td>
							<td>不稳定</td>
							<td>较复杂</td>
						</tr>
						<tr>
							<td>直接选择排序</td>
							<td>O(n2)O(n2)</td>
							<td>O(n2)O(n2)</td>
							<td style='text-align:center;'>O(n2)O(n2)</td>
							<td>O(1)O(1)</td>
							<td>不稳定</td>
							<td>简单</td>
						</tr>
						<tr>
							<td>堆排序</td>
							<td>O(nlog2n)O(nlog2n)</td>
							<td>O(nlog2n)O(nlog2n)</td>
							<td style='text-align:center;'>O(nlog2n)O(nlog2n)</td>
							<td>O(1)O(1)</td>
							<td>不稳定</td>
							<td>较复杂</td>
						</tr>
						<tr>
							<td>冒泡排序</td>
							<td>O(n2)O(n2)</td>
							<td>O(n2)O(n2)</td>
							<td style='text-align:center;'>O(n)O(n)</td>
							<td>O(1)O(1)</td>
							<td>稳定</td>
							<td>简单</td>
						</tr>
						<tr>
							<td>快速排序</td>
							<td>O(nlog2n)O(nlog2n)</td>
							<td>O(n2)O(n2)</td>
							<td style='text-align:center;'>O(nlog2n)O(nlog2n)</td>
							<td>O(nlog2n)O(nlog2n)</td>
							<td>不稳定</td>
							<td>较复杂</td>
						</tr>
						<tr>
							<td>归并排序</td>
							<td>O(nlog2n)O(nlog2n)</td>
							<td>O(nlog2n)O(nlog2n)</td>
							<td style='text-align:center;'>O(nlog2n)O(nlog2n)</td>
							<td>O(n)O(n)</td>
							<td>稳定</td>
							<td>较复杂</td>
						</tr>
						<tr>
							<td>基数排序</td>
							<td>O(d(n+r))O(d(n+r))</td>
							<td>O(d(n+r))O(d(n+r))</td>
							<td style='text-align:center;'>O(d(n+r))O(d(n+r))</td>
							<td>O(n+r)O(n+r)</td>
							<td>稳定</td>
							<td>较复杂</td>
						</tr>
					</tbody>
				</table>
			</figure>
			<h3>① 插入排序</h3>
			<p>•思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。</p>
			<p>	•关键问题：在前面已经排好序的序列中找到合适的插入位置。</p>
			<p>	•方法：</p>
			<p>	 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;–直接插入排序</p></p>
			<p>	&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;–二分插入排序</p></p></p>
			<p>	&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;–希尔排序</p>
			<p><strong>(1)直接插入排序</strong>（从后向前找到合适位置后插入）</p>
			<p> 1、基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。</p>
			<p>代码位置：<a href='https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/insert/DirectInsertSort.java'
				 target='_blank' class='url'>https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/insert/DirectInsertSort.java</a></p>
			<p>&nbsp;</p>
			<p><strong>(2)二分法插入排序</strong>（按二分法找到合适位置插入）</p>
			<p> 1、基本思想：二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。</p>
			<p>代码位置：<a href='https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/insert/BinaryInsertSort.java'
				 target='_blank' class='url'>https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/insert/BinaryInsertSort.java</a></p>
			<p><strong>(3)希尔排序</strong></p>
			<p> 1、基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2</p>
			<p>代码位置：<a href='https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/insert/ShellSort.java'
				 target='_blank' class='url'>https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/insert/ShellSort.java</a></p>
			<p>&nbsp;</p>
			<h3><strong>②</strong> 选择排序</h3>
			<p>•思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。
				•关键问题：在剩余的待排序记录序列中找到最小关键码记录。
				•方法：
				–直接选择排序
				–堆排序</p>
			<p><strong>(1)直接选择排序</strong></p>
			<p>1、基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。</p>
			<p>代码位置：<a href='https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/select/DirectSelectSort.java'
				 target='_blank' class='url'>https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/select/DirectSelectSort.java</a></p>
			<p><strong>(2)堆排序</strong></p>
			<p>1、基本思想：</p>
			<p>　　堆排序是一种树形选择排序，是对直接选择排序的有效改进。</p>
			<p>　　堆的定义下：具有n个元素的序列 （h1,h2,…,hn),当且仅当满足（hi&gt;=h2i,hi&gt;=2i+1）或（hi&lt;=h2i,hi&lt;=2i+1）
				(i=1,2,…,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。</p>
			<p>　　思想：初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。</p>
			<p>代码位置：<a href='https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/select/HeapSort.java'
				 target='_blank' class='url'>https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/select/HeapSort.java</a></p>
			<p>&nbsp;</p>
			<p>&nbsp;</p>
			<h2><strong>③ 交换排序</strong></h2>
			<p><strong>(1)冒泡排序</strong></p>
			<p>1、基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，<a href='https://www.baidu.com/s?wd=%E8%87%AA%E4%B8%8A%E8%80%8C%E4%B8%8B&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd'>自上而下</a>对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。</p>
			<p>代码位置：<a href='https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/exchange/BubbleSort.java'
				 target='_blank' class='url'>https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/exchange/BubbleSort.java</a></p>
			<p><strong>(2)快速排序</strong></p>
			<p>1、基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。</p>
			<p>代码位置：<a href='https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/exchange/QuickSort.java'
				 target='_blank' class='url'>https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/exchange/QuickSort.java</a></p>
			<h2><strong>④ 归并排序</strong></h2>
			<p>1、基本思想:归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。</p>
			<p>代码位置：<a href='https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/merge/MergeSort.java'
				 target='_blank' class='url'>https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/merge/MergeSort.java</a></p>
			<h2><strong>⑤ 基数排序</strong></h2>
			<p>1、基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。</p>
			<p>代码位置：<a href='https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/radix/RadixSort.java'
				 target='_blank' class='url'>https://gitee.com/cdcoder/algorithm/blob/master/src/main/java/cn/cdcoder/solr/radix/RadixSort.java</a></p>
			<p>&nbsp;</p>

		</div>
		<footer>
			<p>Design by <a href="http://cdcoder.cn" target="_blank">徐思润个人博客</a> </p>
			<p>备案号：<a href="/">蜀ICP备15014105号-1</a></p>
			<script type="text/javascript" src="https://s96.cnzz.com/z_stat.php?id=1277229191&web_id=1277229191"></script>
		</footer>
		<script src="../js/rainbow.min.js"></script>
		<script src="../js/java_h.js"></script>
	</body>
</html>
